// 递归
// 本质是：解决主问题时，发现相同子问题，解决主问题和子问题的方法相同
// 心理暗示：宏观看待递归问题，把递归函数当成黑盒，相信这个黑盒一定能完成任务
// 技巧：
//      找到重复子问题 -> 设计函数头
//      子问题是如何解决的 -> 函数体的书写
//      注意递归函数的出口 -> 关注问题不能分割的情况
// 拓展：如果一个题目可以用决策树画出来，那么也可以通过递归解决

// 例题 2：
// 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
//
//        示例 1：
//
//        输入：l1 = [1,2,4], l2 = [1,3,4]
//        输出：[1,1,2,3,4,4]
//        示例 2：
//
//        输入：l1 = [], l2 = []
//        输出：[]
//        示例 3：
//
//        输入：l1 = [], l2 = [0]
//        输出：[0]
//
//
//        提示：
//
//        两个链表的节点数目范围是 [0, 50]
//        -100 <= Node.val <= 100
//        l1 和 l2 均按 非递减顺序 排列

// 解题思路：
// 可借助一个虚拟头结点，每次都进行尾插
// 拿两个链表的头节点的值进行比较，小的尾插到新链表后面
// 剩下的执行继续合并两个链表操作

// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public class MergeTwoLists {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null) return list2;
        if(list2 == null) return list1;
        ListNode head = new ListNode();
        ListNode cur = head;
        if(list1.val <= list2.val){
            cur.next = list1;
            list1 = list1.next;
        }else{
            cur.next = list2;
            list2 = list2.next;
        }
        cur = cur.next;
        cur.next = mergeTwoLists(list1, list2);
        return head.next;
    }
}
